#include <stdlib.h>
#include <assert.h>
#include "RBtree.h"
#define RED 'R'
#define BLACK 'B'

struct RBtree {
	struct node *root;
	struct node *biggest;
	struct node *nil;
};

void LRotate(struct RBtree* T, struct node* n);
void RRotate(struct RBtree* T, struct node* n);
void RBfix(struct RBtree* T, struct node* n);
struct node* min(struct RBtree* T, struct node* n);

void LRotate(struct RBtree* T, struct node* n)
{
	assert(n->rchild);
	struct node* y;
	y = n->rchild;
	n->rchild = y->lchild;
	if (y->lchild != T->nil)
		y->lchild->parent = n;
	y->parent = n->parent;
	if (n->parent == T->nil)
		T->root = y;
	else
		if (n == n->parent->lchild)
		n->parent->lchild = y;
	else
		n->parent->rchild = y;
	y->lchild = n;
	n->parent = y;
}

void RRotate(struct RBtree* T, struct node* n)
{
	assert(n->lchild);
	struct node* y;
	y = n->lchild;
	n->lchild = y->rchild;
	if (y->rchild != T->nil)
		y->rchild->parent = n;
	y->parent = n->parent;
	if (n->parent == T->nil)
		T->root = y;
	else
		if (n == n->parent->lchild)
		n->parent->lchild = y;
	else
		n->parent->rchild = y;
	y->rchild = n;
	n->parent = y;
}

void* create(struct RBtree** s)
{
	*s = (struct RBtree*) malloc(sizeof(struct RBtree));
	if (*s == NULL) {
		return NULL;
	}
	(*s)->nil = (struct node*) malloc(sizeof(struct node));
	if ((*s)->nil == NULL) {
		return NULL;
	}
	(*s)->biggest = (*s)->nil;
	(*s)->nil->lchild = (*s)->nil;
	(*s)->nil->rchild = (*s)->nil;
	(*s)->nil->parent = (*s)->nil;
	(*s)->nil->color = BLACK;
	(*s)->root = (*s)->nil;
	return *s;
}

void nodedestr(struct RBtree* T, struct node* n)
{
	if (n->lchild != T->nil) {
		nodedestr(T, n->lchild);
		free(n->lchild);
	}
	if (n->rchild != T->nil) {
		nodedestr(T, n->rchild);
		free(n->rchild);
	}
}

void destroy(struct RBtree** T)
{
	if (*T != NULL) {
		nodedestr(*T, (*T)->root);
		if ((*T)->root != (*T)->nil)
			free((*T)->root);
		free((*T)->nil);
		free(*T);
		*T = NULL;
	}
}

void removeBP(struct RBtree* T, struct node* n)
{
	struct node* y = T->nil;
	struct node* x = T->nil;
	if (T->biggest == n) {
		T->biggest = T->nil;
	}
	if ((n->lchild == T->nil) || (n->rchild == T->nil))
		y = n;
	else
		y = min(T, n->rchild);

	if (y->lchild != T->nil)
		x = y->lchild;
	else
		x = y->rchild;
	x->parent = y->parent;

	if (y->parent == T->nil) {
		T->root = x;
	} else {
		if (y == y->parent->lchild)
			y->parent->lchild = x;
		else
			y->parent->rchild = x;
	}
	if (y != n)
		n->id = y->id;
	if (y->color == BLACK) {
		RBfix(T, x);
	}
	free(y);
}

int heightN(struct node* n)
{
	if ((n->lchild != n) || (n->lchild != n)) {
		int h1 = heightN(n->lchild);
		int h2 = heightN(n->rchild);
		return((h1 > h2) ? h1 : h2) + 1;
	}
	return 0;
}

int heightT(struct RBtree* T)
{
	return heightN(T->root);
}

struct node* min(struct RBtree* T, struct node* n)
{
	struct node* tmp = n;
	assert(n);
	while (tmp->lchild != T->nil) {
		tmp = tmp->lchild;
	}
	return tmp;
}

struct node* insert(struct RBtree* T, size_t id, void* data)
{
	struct node* n;
	struct node* par = 0;
	struct node* try = 0;
	struct node* ret;
	n = (struct node*) malloc(sizeof(struct node));
	if (n == NULL) {
		return n;
	}
	ret = n;
	n->id = id;
	n->data = data;
	if (T->biggest == T->nil) {
		try = T->root;
		par = T->nil;
		while (try != T->nil) {
			par = try;
			if (id < try->id)
				try = try->lchild;
			else
				try = try->rchild;
		}
	} else {
		par = T->biggest;
	}
	n->parent = par;
	if (par == T->nil) {
		T->root = n;
	} else {
		if (id < par->id)
			par->lchild = n;
		else
			par->rchild = n;

	}
	n->lchild = T->nil;
	n->rchild = T->nil;
	n->color = RED;
	struct node* y;
	while ((n != T->root)&&((n->parent)->color == RED)) {
		if (n->parent == n->parent->parent->lchild) {
			y = n->parent->parent->rchild;
			if ((y)&&(y->color == RED)) {
				n->parent->color = BLACK;
				y->color = BLACK;
				n->parent->parent->color = RED;
				n = n->parent->parent;
			} else {
				if (n == n->parent->rchild) {
					n = n->parent;
					LRotate(T, n);
				}
				n->parent->color = BLACK;
				n->parent->parent->color = RED;
				RRotate(T, n->parent->parent);
			}
		} else {

			y = n->parent->parent->lchild;
			if ((y)&&(y->color == RED)) {
				n->parent->color = BLACK;
				y->color = BLACK;
				n->parent->parent->color = RED;
				n = n->parent->parent;
			} else {
				if (n == n->parent->lchild) {
					n = n->parent;
					RRotate(T, n);
				}
				n->parent->color = BLACK;
				n->parent->parent->color = RED;
				LRotate(T, n->parent->parent);
			}

		}

	}
	T->root->color = BLACK;
	T->biggest = ret;
	return ret;
}

void RBfix(struct RBtree* T, struct node* n)
{
	struct node* w;
	while ((n != T->root)&&(n->color == BLACK)) {
		if (n == n->parent->lchild) {
			w = n->parent->rchild;
			if (w->color == RED) {
				w->color = BLACK;
				n->parent->color = RED;
				LRotate(T, n->parent);
				w = n->parent->rchild;
			}
			if ((w->lchild->color == BLACK)&&(w->rchild->color == BLACK)) {
				w->color = RED;
				n = n->parent;
			} else {
				if (w->rchild->color == BLACK) {
					w->lchild->color = BLACK;
					w->color = RED;
					RRotate(T, w);
					w = n->parent->rchild;
				}
				w->color = n->parent->color;
				n->parent->color = BLACK;
				w->rchild->color = BLACK;
				LRotate(T, n->parent);
				n = T->root;
			}
		} else {
			w = n->parent->lchild;
			if (w->color == RED) {
				w->color = BLACK;
				n->parent->color = RED;
				RRotate(T, n->parent);
				w = n->parent->lchild;
			}
			if ((w->lchild->color == BLACK)&&(w->rchild->color == BLACK)) {
				w->color = RED;
				n = n->parent;
			} else {
				if (w->lchild->color == BLACK) {
					w->rchild->color = BLACK;
					w->color = RED;
					LRotate(T, w);
					w = n->parent->lchild;
				}
				w->color = n->parent->color;
				n->parent->color = BLACK;
				w->lchild->color = BLACK;
				RRotate(T, n->parent);
				n = T->root;
			}
		}
	}
	if (n)
		n->color = BLACK;
}

void* search(struct RBtree* T, size_t id)
{
	struct node* ser = T->root;
	while (ser != T->nil) {
		if (id > ser->id)
			ser = ser->rchild;
		else
			if (id < ser->id)
			ser = ser->lchild;
		else
			return ser->data;
	}
	return NULL;
}

#undef RED
#undef BLACK
